from collections import deque
from functools import cache, lru_cache
from typing import *


class Solution:
    def numberOfStableArrays(self, zero: int, one: int, limit: int) -> int:
        tot = zero + one
        mid = limit + 1

        @cache
        def f(index, one_left, ooo):  # 位置，剩余1，连续1的数量
            if index == tot:
                return 1
            ans = 0
            zero_left = zero - (index - (one - one_left))
            if one_left > 0 and ooo < mid + limit:  # 放1
                ans = f(index + 1, one_left - 1, ooo + 1 if ooo >= mid else mid + 1)
            if zero_left > 0 and ooo > 1:
                ans += f(index + 1, one_left, ooo - 1 if ooo <= mid else mid - 1)

            return ans % 1000000007

        return f(0, one, mid)


class Solution:
    def numberOfStableArrays(self, zero: int, one: int, limit: int) -> int:
        tot = zero + one
        mid = limit + 1

        @lru_cache
        def f(index, one_left, ooo):  # 位置，剩余1，连续1的数量
            if index == tot:
                return 1
            ans = 0
            zero_left = zero - (index - (one - one_left))
            if one_left > 0 and ooo < mid + limit:  # 放1
                ans = f(index + 1, one_left - 1, ooo + 1 if ooo >= mid else mid + 1)
            if zero_left > 0 and ooo > 1:
                ans += f(index + 1, one_left, ooo - 1 if ooo <= mid else mid - 1)

            return ans % 1000000007

        return f(0, one, mid)


s = Solution()
print(s.numberOfStableArrays(zero=3, one=3, limit=2))
# print(s.numberOfStableArrays(zero=1, one=2, limit=1))
# arr = []
# for i in range(10):
#     arr.append(i)
# print(arr)
# arr.pop()
# print(arr)
